UVa/11464 - Even parity/11464.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <map>
  19 #include <set>
  20
  21 #define D(x) cout << #x " is " << x << endl
  22
  23 bool p[15][15];
  24 bool backup[15][15];
  25 bool can_change[15][15];
  26 int n;
  27
  28 #define inside(i, j) (0 <= (i) && (i) < n && 0 <= (j) && (j) < n)
  29
  30 void attack(int i, int j){
  31   if (can_change[i][j]){
  32     if (inside(i-1, j)) p[i-1][j] = !p[i-1][j];
  33     if (inside(i+1, j)) p[i+1][j] = !p[i+1][j];
  34     if (inside(i, j-1)) p[i][j-1] = !p[i][j-1];
  35     if (inside(i, j+1)) p[i][j+1] = !p[i][j+1];
  36   }
  37 }
  38
  39
  40 int main(){
  41   int cases;
  42   scanf("%d", &cases);
  43   for (int C=1; C<=cases; C++){
  44
  45     if (scanf("%d", &n) != 1) return 0;
  46
  47     memset(p, 0, sizeof p);
  48     for (int i=0; i<n; ++i){
  49       for (int j=0; j<n; ++j){
  50         int x;
  51         scanf("%d", &x);
  52         can_change[i][j] = true;
  53         if (x)  attack(i, j);
  54         can_change[i][j] = !x;
  55       }
  56     }
  57
  58     memcpy(backup, p, sizeof p);
  59
  60     int ans = INT_MAX;
  61     //Brute-force the subset of cells to change in the first row
  62     for (int subset=0; subset<(1<<n); ++subset){
  63       memcpy(p, backup, sizeof backup);
  64       int cnt = 0;
  65       for (int j=0; j<n; ++j){
  66         if (subset & (1 << j)){
  67           attack(0, j);
  68           cnt++;
  69         }
  70       }
  71
  72       //Now, deduce the moves for next rows
  73       for (int i=1; i<n; ++i){
  74         for (int j=0; j<n; ++j){
  75           if (p[i-1][j]){
  76             attack(i, j);
  77             cnt++;
  78           }
  79         }
  80       }
  81
  82       //Let's see if this solved it.
  83       bool ok = true;
  84       for (int i=0; i<n; ++i)
  85         for (int j=0; j<n; ++j)
  86           ok &= !p[i][j];
  87
  88
  89       if (ok) ans = min(ans, cnt);
  90
  91     }
  92     printf("Case %d: %d\n", C, (ans < INT_MAX ? ans : -1));
  93   }
  94   return 0;
  95 }